package al53maxsubArrays;

public class MaxSubArray1 {

    // O(n的平方) 被淘汰；
    public static int maxSubArray(int[] nums) {

        if (nums==null){
            return 0;
        }
        int max = nums[0];

        int[] prefixArray = new int[nums.length];
        int prefix = 0;
        for ( int i = 0;i<nums.length;i++){
            prefix += nums[i];
            prefixArray[i] = prefix;
            for (int j = 0; j < i; j++){
                if(prefixArray[i]- prefixArray[j] > max){
                    max = prefixArray[i]- prefixArray[j];
                }
                if(prefixArray[i] > max){
                    max = prefixArray[i];
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {1,4,7,3,12,-4};
        int i = maxSubArray(nums);
        System.out.println(i);
    }
}
